#include <iostream>

using namespace std;

template<typename T, unsigned n>
void Merge(T(*arr)[n], size_t left, size_t r, size_t right)
{
	if (left == right)
		return;
	// create new arrays

	int lnum = r - left + 1, rnum = right - r;
	T* pLarr = new int[lnum]();//这里并没有使用哨兵
	T* pRarr = new int[rnum]();
	int i, j = 0;
	for (i = 0; i < lnum; ++i)
		pLarr[i] = (*arr)[left + i];
	for (i = 0; i < rnum; ++i)
		pRarr[i] = (*arr)[r + 1 + i];

	i = j;
	int k;
	for (k = left; k < right; ++k)
	{
		if (pLarr[i] > pRarr[j])
		{
			(*arr)[k] = pLarr[i];
			++i;
		}
		else
		{
			(*arr)[k] = pRarr[j];
			++j;
		}
	}

	for (;
		i != lnum; ++i, ++k)
		(*arr)[k] = pLarr[i];

	for (;
		j != rnum; ++j, ++k)
		(*arr)[k] = pRarr[j];

	delete[] pLarr;
	delete[] pRarr;
}

template<typename T, unsigned n>
void MergeSort(T(*arr)[n], size_t left, size_t right = n)
{
	if (left >= right)
	{
		cout << (*arr)[right] << " ";
		return;
	}
	int r = (right + left) / 2;

	MergeSort(arr, left, r);
	MergeSort(arr, r + 1, right);

	Merge(arr, left, r, right);
}
////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
//Binary Search
template<typename T, size_t n>
size_t GetArrSize(T (*arr)[n])
{
	return n;
}
template<typename T, size_t n>
int BinarySearch(T(*arr)[n], T& val, size_t low = 0, size_t right = n)
{
	if (low > right)
		return -1;
	int mid = (low + right) / 2;

	if ((*arr)[mid] < val)
		BinarySearch(arr, val, low, mid - 1);
	else if ((*arr)[mid] > val)
		BinarySearch(arr, val, mid + 1, right);
	else
		return mid;
}
int main()
{
	int arr1[] = { 3, 2, 1, 5, 4,9,6,7,8,23,34,45,2341,214,124,0 };
	MergeSort(&arr1, 0);

	int n = 6;

	size_t sub = BinarySearch(&arr1, n);
	return 0;
}
